// Tags: meet-in-mid, Search
#include <cstdio>
#include <map>

typedef unsigned long long ull;
const int N = 36;
int n, m, lim, ans;
ull rec[N], all;
std::map<ull, int> map;

void solve(int step, ull sta, int tot) {
  if (step > lim) {
    if (sta == all) { return ans = std::min(ans, tot), void(); }
    std::map<ull, int>::iterator iter = map.find(sta);
    if (iter != map.end()) map[sta] = std::min(map[sta], tot);
    else
      map[sta] = tot;
    return;
  }
  solve(step + 1, sta, tot), solve(step + 1, sta ^ rec[step], tot + 1);
}

void solve2(int step, ull sta, int tot) {
  if (step > lim) {
    if (sta == all) { return ans = std::min(ans, tot), void(); }
    std::map<ull, int>::iterator iter = map.find(all ^ sta);
    if (iter != map.end()) { ans = std::min(ans, iter->second + tot); }
    return;
  }
  solve2(step + 1, sta, tot), solve2(step + 1, sta ^ rec[step], tot + 1);
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#else
  freopen("P2962 [USACO09NOV]Lights G.in", "r", stdin);
  freopen("P2962 [USACO09NOV]Lights G.out", "w", stdout);
#endif
#endif

  scanf("%d%d", &n, &m);
  for (int i = 1, u, v; i <= m; ++i) {
    scanf("%d%d", &u, &v);
    --u, --v;
    rec[u + 1] |= 1ull << v, rec[v + 1] |= 1ull << u;
  }
  for (int i = 1; i <= n; ++i) rec[i] |= 1ull << (i - 1);
  ans = n;
  all = (1ull << n) - 1ull, lim = n >> 1;
  solve(1, 0, 0);
  lim = n;
  solve2((n >> 1) + 1, 0, 0);
  printf("%d", ans);
  return 0;
}